import functools


# 动态规划二分优化
# class Solution(object):
#     def superEggDrop(self, k, n):
#         DP = [[n for _ in range(n + 1)] for _ in range(k + 1)]
#         for i in range(k + 1):
#             DP[i][0] = 0
#         for i in range(1, k + 1):
#             for j in range(1, n + 1):
#                 left = 1
#                 right = j
#                 while left < right:
#                     mid = (left + right + 1) // 2
#                     if DP[i - 1][mid - 1] <= DP[i][j - mid]:
#                         left = mid
#                     else:
#                         right = mid - 1
#                 DP[i][j] = min(DP[i][j], 1 + max(DP[i - 1][left - 1], DP[i][j - left]))
#                 if left + 1 <= j:
#                     left += 1
#                     DP[i][j] = min(DP[i][j], 1 + max(DP[i - 1][left - 1], DP[i][j - left]))
#         return DP[k][n]

# 记忆化搜索，二分优化
class Solution(object):
    def superEggDrop(self, k, n):
        d = dict()
        self.max = n
        def dfs(k, n):
            if (k, n) in d:
                return d[(k, n)]
            else:
                if n == 0:
                    d[(k, n)] = 0
                    return 0
                if k == 0:
                    d[(k, n)] = self.max
                    return self.max
                left = 1
                right = n
                while left < right:
                    mid = (left + right + 1) // 2
                    if dfs(k - 1, mid - 1) > dfs(k, n - mid):
                        right = mid - 1
                    else:
                        left = mid
                d[(k, n)] = 1 + max(dfs(k - 1, left - 1), dfs(k, n - left))
                if left + 1 <= n:
                    left += 1
                    d[(k, n)] = min(d[(k, n)], 1 + max(dfs(k - 1, left - 1), dfs(k, n - left)))
                return d[(k, n)]
        return dfs(k, n)

data = Solution()
# k = 3
# n = 14
# print(data.superEggDrop(k, n))
k = 1
n = 3
print(data.superEggDrop(k, n))